#include "bits/stdc++.h"
using namespace std;
namespace EXBSGS {
	using i64 = long long;

	int power(int a, int b, int p) {
		int ret = 1;
		while (b > 0) {
			if (b & 1) {
				ret = 1ll * ret * a % p;
			}
			b >>= 1;
			a = 1ll * a * a % p;
		}
		return ret;
	}

	int exgcd(int a, int b, int &x, int &y) {
		if (!b) {
			x = 1, y = 0;
			return a;
		}
		int d = exgcd(b, a % b, y, x);
		y -= a / b * x;
		return d;
	}

	int inv(int a, int p) {
		int x, y;
		exgcd(a, p, x, y);
		return (x % p + p) % p;
	}

	int solve(int a, int b, int p) {
		if (1 % p == b % p) {
      return 0;
		}
		if (a % p == 0 && b) {
			return -1;
		}
		a %= p, b %= p;
		unordered_map<int, int> mp;
		int B = sqrt(p) + 1;
		int t = power(a, B, p);

		for (int i = 0; i <= B; i++) {
			mp[b] = i;
			b = 1ll * b * a % p;
		}

		b = 1;
		for (int i = 1; i <= B; i++) {
			b = 1ll * b * t % p;
			if (mp.count(b)) {
				return i * B - mp[b];
			}
		}
		return -1;
	} 

	int work(int a, int b, int p) {
		int g = __gcd(a, p), ret = 0;
		i64 t = 1;
		a %= p, b %= p;
		if (1 % p == b % p) {
      return 0;
		}
		while (g != 1) {
			if (b % g) {
				return -1;
			}
			ret++;
			p /= g;
			b /= g;
			t = a / g * t % p;
			if (t == b) {
				return ret;
			}
			g = __gcd(a, p);
		}
		int ret2 = solve(a, (int)(1ll * b * inv(t, p) % p), p);
		if (ret2 == -1) {
			return -1;
		}
		return ret2 + ret;
	}
}
